package basic.study.algorithms.solution.recall;

import java.util.LinkedList;
import java.util.Stack;

/**
 * @author Kevin
 * @date 2020/2/17 21:10
 * 正则表达式匹配
 * 假设正则表达式中只包含“*”和“?”这两种通配符，并且对这两个通配符的语义稍微做些改变，其中，“*”匹配任意多个（大于等于 0 个）任意字符，“?”匹配零个或者一个任意字符
 * 判断一个给定的文本，能否跟给定的正则表达式匹配
 */
public class Pattern {
    private boolean matched = false;
    private char[] pattern;//正则表达式
    private int plan;//正则表单式长度

    public Pattern(char[] pattern, int plan) {
        this.pattern = pattern;
        this.plan = plan;
    }

    public boolean match(char[] text, int tlen) {// 文本串及长度
        matched = false;
        rmatch(0, 0, text, tlen);
        return matched;
    }

    private void rmatch(int ti, int pj, char[] text, int tlen) {

        if (matched) return ;// 如果已经匹配了，就不要继续递归了
        if (pj == plan) {//正则表达式到结尾了
            if (ti == tlen) matched = true;// 文本串也到结尾了
            return;
        }
        if (pattern[pj] == '*') {// *匹配任意个字符
            for (int k = 0; k <= tlen - ti; k++) {
                rmatch(ti+k, pj+1, text, tlen);
            }
        } else if (pattern[pj] == '?') {//?匹配0个或者1个字符
            rmatch(ti, pj+1, text, tlen);
            rmatch(ti+1, pj+1, text, tlen);
        } else if (ti < tlen && pattern[pj] == text[ti]) {// 纯字符匹配才行
            rmatch(ti+1, pj+1, text, tlen);
        }
    }
}
